package 剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;

import org.junit.Test;

public class _56_2数组中数字出现的次数 {
	@Test
	public void test() {	
		
		int nums[] = {4,4,2,4,2,2,1};
		System.out.println(singleNumber1(nums));
	}
	/**
	 * 
	 *@time 2021年3月23日下午7:18:34
	 * 
	 *@param nums
	 *@return int
	 *
	 *@see目前还处于懵逼状态
	 */
    public int singleNumber1(int[] nums) {
		int one = 0,two = 0;
    	for (int num : nums) {
			one = one ^ num & ~two;
			two = two ^ num & ~one;
		}
    
    	return one;

    }
    /**
     * 
     *@time 2021年3月23日下午6:58:28
     * 
     *@param nums
     *@return int
     *
     *@see 考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
	 *因此，统计所有数字的各二进制位中 11 的出现次数，并对 3 求余，结果则为只出现一次的数字。
     */
    public int singleNumber2(int[] nums) {
    	int []counts = new int[32];
    	for (int num : nums) {   		
			for (int i = 0; i < 32; i++) {
				counts[i] += num & 1;
				num >>>= 1;
			}
		}
    	int res = 0;
    	for (int i = 0; i < 32; i++) {
			res <<= 1;
			res |= counts[31-i]%3;
		}
    	return res;
    }
    /**
     * 
     *@time 2021年3月23日下午7:23:18
     * 
     *@param nums
     *@return int
     *
     *@see常规的方法，时间复杂度比较高
     */
    public int singleNumber3(int[] nums) {
    	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    	for (int i : nums) {
			if(map.containsKey(i)) map.put(i,map.get(i)+1);
			else map.put(i,1);
		}
    	for (Entry<Integer, Integer> entry : map.entrySet()) {
			if(entry.getValue()==1) return entry.getKey();
		}
		return -1;
    	
    }
    /**
     * 
     *@time 2021年3月23日下午7:25:31
     * 
     *@param nums
     *@return int
     *
     *@see 排完序，                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
     */
    public int singleNumber4(int[] nums) {
    	Arrays.sort(nums);
    	for (int i = 1; i < nums.length; i++) {
			if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]) return nums[i];
		}
        if(nums[0] != nums[1]) return nums[0];
        return nums[nums.length-1];
    }
    
    
}
